'''
行程长度编码 是一种常用的字符串压缩方法，它将连续的相同字符（重复 2 次或更多次）替换为字符和表示字符计数的数字（行程长度）。
例如，用此方法压缩字符串 "aabccc" ，将 "aa" 替换为 "a2" ，"ccc" 替换为` "c3" 。因此压缩后的字符串变为 "a2bc3" 。
注意，本问题中，压缩时没有在单个字符后附加计数 '1' 。
给你一个字符串 s 和一个整数 k 。你需要从字符串 s 中删除最多 k 个字符，以使 s 的行程长度编码长度最小。
请你返回删除最多 k 个字符后，s 行程长度编码的最小长度 。

示例 1：
输入：s = "aaabcccd", k = 2
输出：4
解释：在不删除任何内容的情况下，压缩后的字符串是 "a3bc3d" ，长度为 6 。最优的方案是删除 'b' 和 'd'，这样一来，压缩后的字符串为 "a3c3" ，长度是 4 。

示例 2：
输入：s = "aabbaa", k = 2
输出：2
解释：如果删去两个 'b' 字符，那么压缩后的字符串是长度为 2 的 "a4" 。

示例 3：
输入：s = "aaaaaaaaaaa", k = 0
输出：3
解释：由于 k 等于 0 ，不能删去任何字符。压缩后的字符串是 "a11" ，长度为 3 。

提示：
    1 <= s.length <= 100
    0 <= k <= s.length
    s 仅包含小写英文字母
'''


def getLengthOfOptimalCompression(s: str, k: int) -> int:
    n = len(s)

    # 计算数字的位数，用于编码长度计算
    def count_digits(x):
        if x <= 1:
            return 0
        elif x < 10:
            return 1
        elif x < 100:
            return 2
        else:
            return 3

    # dp[i][j][last][cnt] 表示前i个字符，删除j个，最后一个字符是last，连续出现cnt次的最小编码长度
    # 为了节省空间，使用字典存储状态
    from collections import defaultdict

    # 初始状态：处理0个字符，删除0个，没有最后字符，计数为0，编码长度0
    dp = [defaultdict(lambda: float('inf')) for _ in range(k + 1)]
    dp[0][(None, 0)] = 0

    for i in range(n):
        # 下一个状态
        next_dp = [defaultdict(lambda: float('inf')) for _ in range(k + 1)]

        for delete in range(k + 1):
            for (last_char, count), length in dp[delete].items():
                # 选项1：删除当前字符
                if delete < k:
                    key = (last_char, count)
                    if next_dp[delete + 1][key] > length:
                        next_dp[delete + 1][key] = length

                # 选项2：保留当前字符
                current_char = s[i]
                if current_char == last_char:
                    # 与前一个字符相同，增加计数
                    new_count = count + 1
                    # 计算编码长度变化：只有当计数从1→2、9→10、99→100时，长度才会增加
                    added_length = 0
                    if count == 1:
                        added_length = 1  # 从1到2，需要添加数字"2"
                    elif count == 9:
                        added_length = 1  # 从9到10，数字位数增加1
                    elif count == 99:
                        added_length = 1  # 从99到100，数字位数增加1

                    new_length = length + added_length
                    key = (current_char, new_count)
                    if next_dp[delete][key] > new_length:
                        next_dp[delete][key] = new_length
                else:
                    # 与前一个字符不同，增加一个新的编码单元
                    new_count = 1
                    new_length = length + 1  # 只增加字符本身，不增加计数（因为是1）
                    key = (current_char, new_count)
                    if next_dp[delete][key] > new_length:
                        next_dp[delete][key] = new_length

        dp = next_dp

    # 找到所有可能状态中的最小长度
    min_length = float('inf')
    for delete in range(k + 1):
        for length in dp[delete].values():
            if length < min_length:
                min_length = length

    return min_length


# 测试示例
if __name__ == "__main__":
    test_cases = [
        ("aaabcccd", 2, 4),
        ("aabbaa", 2, 2),
        ("aaaaaaaaaaa", 0, 3),
        ("abc", 0, 3),
        ("aabbcc", 3, 2)
    ]

    for s, k, expected in test_cases:
        result = getLengthOfOptimalCompression(s, k)
        print(f"输入: s = {s}, k = {k}")
        print(f"输出: {result}, 预期: {expected}")
        print("-" * 50)
